home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.09 / ChallengeTuring.sit.hqx / Challenge, Turing / turing.cp next >
Text File  |  1997-06-01  |  8KB  |  278 lines
  1. /*
  2.  
  3.   May 31 1997.
  4.   Submission to MacTech Programmer's challenge for June97.
  5.   Copyright 1997, Ernst Munter, Kanata, ON, Canada.
  6.  
  7.                   "Turing Machine"
  8.           
  9. Version 2:
  10.   A few minor tweaks for a 5% gain in speed.          
  11.                   
  12.   Problem Statement
  13.   -----------------
  14.   Implement the engine for a Turing Machine, a state machine
  15.   which, at each step, reads a symbol from a tape, consults
  16.   a rule which is a function of the current state and the
  17.   symbol. The rule specifies a new state, a symbol to output,
  18.   and the direction in which to move the tape, or to halt.
  19.  
  20.   Solution
  21.   --------
  22.   I first try to build a lookup table as an index into the
  23.   rules array.  But this may require an "unreasonable"
  24.   amount of memory.
  25.  
  26.   First, I scan the rules to determine the amount of table
  27.   memory required for a simple lookup index.  If this
  28.   appears to be too much, I go to plan B: a hashed index.
  29.  
  30.   The hash table uses linear open addressing: when the table
  31.   is built and an index location is needed which is already
  32.   in use we have a collision. To resolve it, I scan linearly
  33.   through the index array until a free location is found.
  34.   The size of the index array is larger than the number of
  35.   rules, so a free location will always be found.
  36.  
  37.   Optimization of hash table lookup
  38.   ---------------------------------
  39.   The majority of rules will hash to unique index addresses.
  40.  
  41.   Rules which hash to the same value can be seen as a
  42.   sequence of index table entries, with the primary location
  43.   containing the first rule address to be found.
  44.  
  45.   When the Turing Machine is executing, any colliding rule
  46.   that is encountered will have its index moved to the
  47.   primary index location, on the assumption that it will be
  48.   used again, and will then be found more quickly.
  49.  
  50.   Assumptions
  51.   -----------
  52.   A minimum amount of table memory of 8K entries is always
  53.   provided.  But for larger rule sets, an index table that
  54.   will occupy about 1/2 to 3/4 the amount of memory taken
  55.   by the rules array itself may be allocated.
  56.  
  57.   The memory allocated for the simple lookup table will be
  58.   the number_of_states * number_of_symbols, rounded up to
  59.   a power of 2, but not more than 8K entries,
  60.   or 2 * number_of_rules, whichever is larger.
  61.  
  62.   If the memory required for the simple index would exceed
  63.   those rules, for example if there are a lot of holes
  64.   in the symbol/state space, the hashed index is used.
  65.  
  66.   The memory allocated for the hash index array will
  67.   be the larger of 8K entries or 2 * number_of_rules, rounded
  68.   up to the nearest power of 2.
  69.  
  70.   For example, a rule set of up to 2K rules may result in
  71.   a 32K byte index;  a rule set of 50,000 rules which occupy
  72.   1M of rules memory may get an index table of 512K bytes.
  73.  
  74. */
  75.  
  76. #include <stdio.h>
  77.  
  78. #include <stdlib.h>
  79. #include <string.h>
  80. #include "turing.h"
  81.  
  82. const enum {        // constants controlling min size of index
  83.     EXPANSION    = 2,
  84.     MIN_BITS     = 13,
  85.     MIN_SIZE    = 1L<<MIN_BITS };    
  86.     
  87. typedef const TMRule* TMRulePtr;
  88.  
  89. Boolean TuringMachine(
  90.   const TMRule theRules[],
  91.   ulong numRules,
  92.   ulong *theTape,
  93.   ulong tapeLen,
  94.   long rwHeadPos,
  95.   TMMoveProc ReportMove
  96. ) {
  97.   TMRulePtr* index;
  98.   ulong        state=0;
  99.   ulong        symbol;
  100.   int        direction;
  101.   ulong*    tape=theTape+rwHeadPos;
  102.   ulong*    tapeEnd=theTape+tapeLen;
  103.  
  104.   ulong        mask;
  105.   TMRulePtr rule=theRules;
  106.  
  107. // The function contains 2 very similar sections,
  108. // one section uses a plain lookup table for an index,
  109. // the other uses a hash table.
  110.  
  111. // Try to construct a collision-free index of rule addresses
  112.  
  113. // compute table size
  114.   ulong     maxState=rule->oldState;
  115.   ulong     maxSym=rule->inputSymbol;
  116.   ulong     minSym=rule->inputSymbol;
  117.   rule++;
  118.   for (int i=1;i<numRules;i++) {
  119.     if (maxState<rule->oldState) maxState=rule->oldState;
  120.     if (maxSym<rule->inputSymbol) maxSym=rule->inputSymbol;
  121.     else
  122.     if (minSym>rule->inputSymbol) minSym=rule->inputSymbol;
  123.     rule++;
  124.   }
  125.   ulong numSyms=maxSym-minSym+1;
  126.   ulong numStates=maxState+1;
  127.   ulong numIndex=(numStates)*(numSyms);
  128.  
  129.   if ((numIndex<numStates)                 // overflow
  130.     || ((numIndex > MIN_SIZE)
  131.     && (numIndex > EXPANSION*numRules)))// too large
  132.       goto try_hash;
  133.  
  134. // increase size to the next power of 2
  135.   ulong dummy=1;
  136.   while (numIndex) {
  137.     numIndex>>=1;
  138.     dummy<<=1;
  139.   }
  140.   numIndex=dummy;
  141.  
  142. // Allocate the table memory
  143.   index=(TMRulePtr*)malloc(numIndex*sizeof(TMRulePtr));
  144.  
  145. // Always expect to get the memory, but just in case ...
  146.   if (index==0)
  147.     return FALSE;
  148.  
  149. // All unused index locations will remain 0
  150.   memset(index,0,numIndex*sizeof(TMRulePtr));
  151.   mask=numIndex-1;
  152.  
  153. // Scan the rules and populate the index array
  154.   rule=theRules;
  155.   for (int i=0;i<numRules;i++) {
  156.     ulong addr=mask & (rule->oldState*numSyms+rule->inputSymbol);
  157.     index[addr]=rule++;
  158.   }
  159. // Using the collision-free index table:
  160. // Loop until the tape halts or we fail on error
  161.   do {
  162.       symbol=*tape;
  163.       ulong addr=mask & (state*numSyms+symbol);
  164.       rule=index[addr];
  165.       if (rule == 0)        // illegal symbol, no rule
  166.         break;
  167.       symbol=rule->outputSymbol;
  168.       state=rule->newState;
  169.       direction=rule->moveDirection;
  170.  
  171.       ReportMove(symbol,state,MoveDir(direction));
  172.  
  173.       *tape=symbol;
  174.  
  175.       if (direction==kHalt)   {
  176.         free(index);
  177.         return TRUE;    
  178.       }    
  179.           
  180.       tape+=direction;
  181.   } while ((tape>=theTape) && (tape<tapeEnd));
  182.   free(index);
  183.   return FALSE;
  184.  
  185.  
  186. try_hash:
  187. // Section 2
  188. // If we get here, we could not make a simple table
  189. // and have to go with a hash table, collisions are possible
  190.  
  191. // Find table size >= minimum size
  192.   numIndex=MIN_SIZE;
  193.   while (numIndex < EXPANSION*numRules) {
  194.     numIndex*=2;
  195.   }
  196.  
  197. // Allocate the table memory
  198.   index=(TMRulePtr*)malloc(numIndex*sizeof(TMRulePtr));
  199.  
  200. // Always expect to get the memory, but just in case ...
  201.   if (index==0)
  202.     return FALSE;
  203.  
  204. // All unused index locations will remain 0
  205.   memset(index,0,numIndex*sizeof(TMRulePtr));
  206.  
  207.   mask=numIndex-1;
  208.   ulong     hFactor=1 | (numIndex/numStates);
  209.   long         hDelta=1 | (hFactor>>1);
  210.  
  211. // Scan the rules and populate the index array
  212.   rule=theRules;
  213.   for (int i=0;i<numRules;i++) {
  214.     ulong addr=mask & (rule->oldState*hFactor+rule->inputSymbol);
  215.  
  216. // if primary location is not empty: find next free location
  217.     while (index[addr])     
  218.       addr=mask & (addr+hDelta);
  219.  
  220.     index[addr]=rule++;
  221.   }
  222.  
  223. // Using the hash index table:
  224. // Loop until the tape halts or we fail on error.
  225.  
  226. // This loop is the same as the loop in the first section
  227. // except we have to check for possible collisions with each rule..
  228.   do {
  229.       symbol=*tape;
  230.       ulong addr=mask & (state*hFactor+symbol);
  231.       rule=index[addr];
  232.       if (rule == 0)            // illegal symbol, no rule
  233.         break;
  234.     
  235. // check if we have the right rule, or a collision    
  236.       if ((symbol != rule->inputSymbol)
  237.         || (state != rule->oldState)) {    
  238.          const TMRule* rule0=rule;
  239.         ulong addr0=addr;
  240.  
  241.         do {                    // resolve the collision
  242.           addr=mask & (addr+hDelta);
  243.           rule=index[addr];
  244.           if (rule == 0) {        // could not find rule
  245.               free(index);
  246.               return FALSE;
  247.             }    
  248.     
  249.         } while ((symbol != rule->inputSymbol)
  250.               || (state != rule->oldState));
  251.         index[addr]=rule0;        // move last-used rule
  252.         index[addr0]=rule;         // up in chain
  253.     
  254.       }
  255.     
  256. // now we have the correct rule    
  257.       symbol=rule->outputSymbol;
  258.       state=rule->newState;
  259.       direction=rule->moveDirection;
  260.  
  261.       ReportMove(symbol,state,MoveDir(direction));
  262.  
  263.       *tape=symbol;
  264.       if (direction==kHalt) {    // normal stop
  265.         free(index);
  266.         return TRUE;    
  267.       }
  268.  
  269.       tape+=direction;
  270.   } while ((tape>=theTape) && (tape<tapeEnd));
  271.  
  272.   free(index);
  273.   return FALSE;
  274. }
  275.  
  276.  
  277.  
  278.